#include "commonInc.h"

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        const int n = nums.size();
        if (n < 3)
            return {};

        std::sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        for (int i = 0; i <= n - 3; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int left = i + 1, right = n - 1;
            while (left < right)
            {
                int twoSum = nums[left] + nums[right];
                if(nums[left] + nums[left+1] > -nums[i])
                    break;
                if(nums[right] + nums[right-1] < -nums[i])
                    break;

                if (twoSum == -nums[i])
                {
                    ans.push_back({nums[i], nums[left], nums[right]});

                    left++;
                    while (left < right && nums[left] == nums[left - 1])
                        left++;

                    right--;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
                else if(twoSum > -nums[i])
                    right--;
                else 
                    left++;
                    
            }
        }
        return ans;
    }
};